//
// Description: 1005. K 次取反后最大化的数组和
// Created by Loading on 2021/12/3.
//

#include <bits/stdc++.h>

using namespace std;

int largestSumAfterKNegations(vector<int> &nums, int k) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    unordered_map<int, int> m;
    for (auto &x : nums) {
        m[x]++;
    }

    // 优先取反负数，由小到大
    for (int i = -100; i < 0; ++i) {
        if (m[i]) {
            // 操作次数
            int cnt = min(m[i], k);
            sum += (-i) * cnt * 2;
            // 更新hash表
            m[-i] += cnt;
            m[i] -= cnt;
            k -= cnt;
            if (k == 0) {
                break;
            }
        }
    }

    // 负数取反完毕，若还有奇数次剩余操作次数，且数组中不存在0，取反一次最小正值即可
    if (k % 2 == 1 && !m[0]) {
        for (int i = 1; i <= 100; ++i) {
            if (m[i]) {
                sum -= i * 2;
                break;
            }
        }
    }

    return sum;
}

int main() {
    vector<int> nums = {4, -5, 4, -5, 9, 4, 5};
    int k = 1;
    int res = largestSumAfterKNegations(nums, k);
    cout << res << endl;

    return 0;
}